package com.lx.algorithm.monotoneStack;

import java.util.Stack;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-08 13:30:46
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-08     张李鑫                     1.0         1.0 Version
 */
//https://leetcode.com/problems/count-submatrices-with-all-ones
public class CountSubmatricesWithAllOnes {

    /**
     * 给定一个二维数组matrix，其中的值不是0就是1，
     * 返回全部由1组成的最大子矩形，内部有多少个1
     */

    public static void main(String[] args) {
        int[][] arr = {
                {0, 1, 1, 0},
                {0, 1, 1, 1},
                {1, 1, 1, 0},
        };
//
//
//        int[][] arr = {
//                {1, 0, 1},
//                {1, 1, 0},
//                {1, 1, 0},
//        };


        System.out.println(numSubmat(arr));
    }


    public static int numSubmat(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) {
            return 0;
        }
        int[] sumArr = new int[mat[0].length];
        int[] arr = new int[mat[0].length];
        MyStack myStack = new MyStack(arr);

        int max = 0;
        for (int i = 0; i < mat.length; i++) {
            for (int i1 = 0; i1 < mat[i].length; i1++) {
                sumArr[i1] = mat[i][i1] == 0 ? 0 : sumArr[i1] + 1;
            }
            max += numSubmat(sumArr, myStack);
        }
        return max;
    }

    public static int numSubmat(int[] sumArr, MyStack myStack) {
        int maxCount = 0;
        for (int i = 0; i < sumArr.length; i++) {
            while (!myStack.isEmpty() && sumArr[myStack.peek()] >= sumArr[i]) {
                int pop = myStack.pop();
                if (sumArr[pop] > sumArr[i]) {
                    int n = myStack.isEmpty() ? i : i - 1 - myStack.peek();
                    int loopCount = myStack.isEmpty() ? sumArr[pop] - sumArr[i] : sumArr[pop] - Math.max(sumArr[myStack.peek()], sumArr[i]);
                    maxCount += loopCount * sum(n);
                }
            }
            myStack.push(i);
        }
        while (!myStack.isEmpty()) {
            int pop = myStack.pop();
            int n = myStack.isEmpty() ? sumArr.length : sumArr.length - 1 - myStack.peek();
            int loopCount = myStack.isEmpty() ? sumArr[pop] : sumArr[pop] - sumArr[myStack.peek()];
            maxCount += loopCount * sum(n);
        }
        return maxCount;
    }


    //实现一个简易的栈 提高性能
    public static class MyStack {
        int[] arr;
        int start;

        public MyStack(int[] arr) {
            this.arr = arr;
            start = -1;
        }

        public int peek() {
            return arr[start];
        }

        public boolean isEmpty() {
            return start == -1;
        }

        public int pop() {
            return arr[start--];
        }

        public void push(int val) {
            arr[++start] = val;
        }
    }


    public static int sum(int n) {
        return ((n + 1) * n) >> 1;
    }
}
